/*
 * @Description: 插入排序算法实现
 * @Version: 
 * @Author: Weixin Zhu
 * @Date: 2020-11-24 13:48:11
 * @LastEditors: Weixin Zhu
 * @LastEditTime: 2020-12-11 17:00:32
 */
package com.zwx.algorithms.basic;

import com.zwx.algorithms.constant.AlgorithmsConstant;
import com.zwx.algorithms.pub.util.AlgorithmsUtils;
import com.zwx.algorithms.pub.util.LogUtils;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import cn.hutool.core.date.DateUtil;
import cn.hutool.core.date.StopWatch;

public class InsertionSort extends AbstractArraySort {
    static final Logger log = LoggerFactory.getLogger(InsertionSort.class);

    /**
     * @description:插入排序算法实现
     * @param {Integer[]}
     *                        array
     * @return {*}
     */
    public Integer[] sort(Integer[] array) {
        int size = array.length;
        for (int i = 1; i < size; i++) {
            int key = array[i];
            // Insert A[i] into the sorted sequence a[1..i-1].
            int j = i - 1;
            while (j > -1 && array[j] > key) {
                totalStep++;
                if (AlgorithmsUtils.needShowStep(size)) {
                    log.debug("index :{},i:{},j:{}", totalStep, i, j);
                }
                array[j + 1] = array[j];
                j = j - 1;
            }
            array[j + 1] = key;
        }

        return array;
    }

    public static void main(String[] args) {
        LogUtils.resetLogLevel(log, org.slf4j.event.Level.INFO);
        Integer[] originArray = null;
        Integer[] sortResult = null;
        AbstractArraySort sort = new InsertionSort();
        StopWatch sw = DateUtil.createStopWatch();
        originArray = AlgorithmsUtils.generateRandomArray(AlgorithmsConstant.MAX_VALUE);
        sw.start();
        sortResult = sort.sort(originArray);
        sw.stop();

        AlgorithmsUtils.printSortedArray(sortResult);
        log.info("size:{},totalStep:{},cost time:{}", sortResult.length, sort.getTotalStep(), sw.getLastTaskTimeMillis());
        log.info(sw.prettyPrint());
    }

}
